In a given communication network, the routing of traffic from a source to a destination can be accomplished by a variety of methods. In the traditional pipe model routing schemes, traffic between network access points is carried through point-to-point pipes having pre-allocated capacities. In one variation of this model, a pipe is allocated for the worst case traffic between each pair of nodes in the network, and the capacities of these pipes are added in order to calculate the required capacity of a link connecting those nodes. In many models, knowledge of the actual traffic in the network (i.e., the traffic matrix) is required in order to route the traffic efficiently.
The traffic matrix is typically difficult to determine, often requiring the use of extensive computing resources. Furthermore, traffic in a network is constantly changing over time, requiring even greater network resources to track and react to the network traffic changes. Ideally, the routing scheme in a network should be changed to accommodate dynamic changes in the traffic matrix. There are often problems with implementing this approach. Unfortunately, it is inherently difficult to change a routing scheme quickly enough to accommodate such dynamic traffic changes.
Since knowing the entire traffic matrix of a network is difficult in practice, there have been alternate approaches to specifying the traffic matrix. One such method that has been recently proposed is the hose model. In the hose model, network traffic is characterized using per-node aggregate ingress and egress traffic volumes instead of using a traffic matrix of point-to-point demands for each pair of nodes in the network. In other words, in the hose model, the ingress and egress capacities are assumed to be known for each of the nodes in a network; however, the exact traffic splits among the nodes are not known. A major criticism of the hose model is that, compared to a network in which the entire traffic demand matrix is known, extensive resources and over-provisioning of capacity are required in order to route traffic.
Tree routing is a variation of the hose model in which a path through a network is computed using a tree approach in which connections through the network are restricted to using a tree subset of the original topology of the network. Since the routing in this case is constrained to the use of a tree, path length can be significantly longer than other variations of the hose model, and additional capacity may be required in order to implement redundancy. Thus, there is no guarantee that the routing algorithm, even an optimal solution to the algorithm, will be bandwidth efficient.
For the case in which the uncertainty of the traffic distribution within a network is high, the flexibility, reduced blocking, decreased traffic loss and ease of specification of the different variations of the hose model make the hose model an attractive alternative to the traditional pipe model of routing. Unfortunately, the over-provisioning currently required to implement the different variations of the hose model, however, is still a major drawback of the hose model, especially since the required over-provisioning factor tends to increase with network size for existing variations of the hose model.